package com.clstu.sort;

import java.util.Arrays;

/**
 * 研究归并排序(分治法, 先左排序,再右排序,再merge)
 */
public class MergeSort {
    private static int count = 0;
    public static void main(String[] args) {
        //测试一下
//        int[] arr = {6,5,4,3,2,16,5,4,3,2,1};
//        int[] tmp = new int[arr.length];
//        mergeSort(arr,0,tmp.length-1,tmp);
//        System.out.println("排序后:"+ Arrays.toString(arr));

        //测试速度
        int[] arr = new int[8000000];
        int[] tmp = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=(int) (Math.random()*80000);
        }
        System.out.println("排序前是否有序:"+isSorted(arr));
        long start = System.currentTimeMillis();
        mergeSort(arr,0,tmp.length-1,tmp);
        long end = System.currentTimeMillis();
        System.out.println("归并排序"+arr.length+"个数据耗时:"+(end-start)+"ms");//14ms
        System.out.println("排序后是否有序:"+isSorted(arr));

        start = System.currentTimeMillis();
        mergeSort(arr,0,tmp.length-1,tmp);
        end = System.currentTimeMillis();
        System.out.println("归并排序"+arr.length+"个数据(有序的)耗时:"+(end-start)+"ms");//4ms
    }

    //编写方法实现merge,即合并两个有数组(使一个数组的两边分别有序)
    public static void merge(int[] arr,int left,int right,int[] tmp){
        //思路,扫描两个有序表,比较两边谁更小,如果左边小,左边的数填到temp末尾的位置,temp指针后移,l后移
        //                             如果右边小,右边的数填到temp末尾的位置,temp指针后移,r后移
        //                      如果有一遍提前遍历完,另一半之间挨着填到temp后面
        int mid = (right+left)/2;
        int l = left;//遍历左边
        int r = mid+1;//遍历右边
        int t = left;//遍历temp
        //遍历合并左右两边的表
        while (true){
            //如果遍历完
            if (l>mid){
                while (r<=right){
                    tmp[t++]=arr[r++];
                }
                break;
            }
            if(r>right){
                while (l<=mid){
                    tmp[t++]=arr[l++];
                }
                break;
            }
            //比较谁小谁被排序
            if(arr[l]<arr[r]){
                tmp[t++]=arr[l++];
            }else {
                tmp[t++]=arr[r++];
            }
        }
        //复制tmp--->arr
        for (int i = left; i <= right ; i++) {
            arr[i] = tmp[i];
        }
        //查看结果
//        System.out.println("第"+(++count)+"次merge后(left="+left+" right="+right+"):"+Arrays.toString(arr));
    }

    //编写方法实现归并排序
    public static void mergeSort(int[] arr, int left,int right,int[] tmp){
        //思路分析:
        //归并排序的思想,反复的将一个数组分为左右两边,将左右两边都排好序之后,
        // 再将左右两个有序的数组合并成一个有序数组tmp中,最后拷贝到arr中

        //如果不用排序
        if(left>=right){
            return;
        }
        int mid = (right+left)/2;
        //左排序
        mergeSort(arr,left,mid,tmp);
        //右排序
        mergeSort(arr,mid+1,right,tmp);
        //归并
        merge(arr,left,right,tmp);
    }

    //编写方法判断两个数组的内容是否一样
    public static boolean same(int[] arr1,int[] arr2){
        for (int i = 0; i < arr1.length&&i<arr2.length; i++) {
            if(arr1[i]!=arr2[i]){
                return false;
            }
        }
        return true;
    }

    //编写方法判断数组是否已经有序
    public static boolean isSorted(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            if(arr[i]>arr[i+1]) return false;
        }
        return true;
    }
}
